COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00007 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A73.Tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 22, 1988}
\leftline{\sevenrm Unpublished draft}

\font\sevenit=cmti7
\scriptfont\itfam=\sevenit

\bigskip
\noindent {\bf Acceptors, Recognizers, and Classifiers}
\medskip
Let $L$ be a language (set of strings) over the alphabet $\Sigma$.
Consider programs with domain $\Sigma↑*$ where $\alpha↓{\it input} =
\gamma$ and $\alpha$ for other devices is independent of
the argument, there is no output device, and the range is $\{\it True, False\}$.
Such a program is called an {\it acceptor} for $L$ if $\tau\circ\{\it True\}
= L$.

It is a {\it co-acceptor} for $L$ if $\tau\circ\{\it False\} = {\overline L}$.
That is, by changing $\omega$ in the obvious way, a co-acceptor for $L$
is an acceptor for ${\overline L}$.  A program is a {\it recognizer} for $L$
if it is deterministic, an acceptor, and a co-acceptor.  By twiddling $\omega$,
a recognizer for $L$ becomes a recognizer for ${\overline L}$.

If such a machine starts and ends with all memory devices in a standard
state (say, stacks and queues empty, counters zero), the definitions of $\alpha$
and $\omega$ for each device are:
$$\eqalign{\alpha↓{\it memory} & =  \Sigma↑* \times \{\it standard\, state\},\cr
\omega↓{\it memory} & =  \{\it standard\, state\} \times \{\it True, False\},\cr
\alpha↓{\it input} & =  \gamma,\cr
\omega↓{\it input} & =  \Lambda\times\{\it True, False\},\cr
\alpha↓{\it control} & =  \Sigma↑*\times Q↓{\it start}, \hbox {where}\; 
Q↓{\it start}
\subseteq Q,\cr
\omega↓{\it control} & =  Q↓{\it accept} \times \{{\it True}\}\cup Q↓{\it reject}
\times \{{\it False}\}, 
\hbox {where}\; Q↓{\it accept} \subseteq Q, Q↓{\it reject}
\subseteq Q.\cr}$$
The notion of a recognizer can be generalized to that of a {\it classifier}, where
the range is a finite set $Y$, and $\omega↓{\it control}$ is a partial function
from $Q$ to $Y$, the program is deterministic, and its transfer function is total.

An acceptor for a language $L$ can easily be transformed into a program that
{\it generates} $L$; replace the input device with an output device, and replace
each instruction in the
acceptor program that scans input, $\langle i\rightarrow j, \hbox {scan}\, a, f
\rangle$, by $\langle i\rightarrow j, \hbox {write}\,
a, f\rangle$.  Notice that a deterministic acceptor, in general, transforms to a
nondeterministic generator.

Similarly, an acceptor for $L$ can be transformed into a transducer with 
transfer relation $\gamma↓L$; add an output device, and replace each
acceptor instruction $\langle i\rightarrow j, \hbox {scan}\, a, f\rangle$ that
scans input by $\langle i\rightarrow j, \hbox {scan}\, a, f, \hbox {write}\,
 a\rangle$.
Such a transducer, which passes from input to output precisely the elements
of the language $L$, is called a {\it filter}.
\bye